题意:一个 个点的图,给定了任意两点之间的不同简单路数量 ,简单路定义为不经过重复点的路径,保证。求构造满足要求的图或判断无解。
画几张图观察一下简单路的性质,发现合法的图一定满足任意一个连通块中最多只有一个环。如果一个连通块有不止一个环,一定可以找到一对点存在至少四条不同简单路,如下图:

那么一个连通块一定是树或者基环树。dfs 出每个连通块,先判断一下如果连通块里出现了路径数为 的点对就是无解。然后树非常好处理,如果连通块内路径数全是 那就是树,随便构造一个就行。基环树复杂一些,我们画张图:

观察发现,如果两个点在同一个红圈里,那它们只间有 条简单路,否则有 条。 是绝对不会出现的,出现了直接无解。然后 dfs 出每个连通块里,由 相连的子连通块,它们应该在一个红圈里。如果一个红圈里混进了路径数为 的点对那无解,否则把它们连成一棵树。最后在每个红圈里找一个代表点,把这些代表点串起来成为一个环即可。如果代表点不足三个就没法串成环,还是无解。
#include "supertrees.h"
#define N 1000
std::vector<std::vector<int>> *G, ret;
void addedge(int x, int y) {
ret[x][y] = ret[y][x] = 1;
}
int n, mx; char vis[N];
std::vector<int> cnt, all, sm;
void dfs(int x) {
vis[x] = 1;
cnt.push_back(x);
for (int i = 0; i < n; i++) {
int d = (*G)[x][i];
mx = std::max(d, mx);
if (!vis[i] && d) dfs(i);
}
}
void dfsS(int x) {
vis[x] = 2;
sm.push_back(x);
for (int i = 0; i < n; i++) {
if (vis[i] == 1 && (*G)[x][i] == 1) dfsS(i);
}
}
int construct(std::vector<std::vector<int>> p) {
G = &p; n = p.size();
ret.resize(n);
for (int i = 0; i < n; i++)
ret[i].resize(n);
for (int i = 0; i < n; i++) if (!vis[i]) {
mx = 1;
cnt.clear();
dfs(i);
if (mx == 3) return 0;
for (int i = 1; i < cnt.size(); i++)
for (int j = 0; j < i; j++)
if (p[cnt[i]][cnt[j]] == 0)
return 0;
if (mx == 1) {
for (int i = 1; i < cnt.size(); i++)
addedge(cnt[0], cnt[i]);
continue;
}
all.clear();
for (int j : cnt) if (vis[j] == 1) {
sm.clear();
dfsS(j);
for (int i = 1; i < sm.size(); i++) {
for (int j = 0; j < i; j++)
if (p[sm[i]][sm[j]] != 1)
return 0;
addedge(sm[0], sm[i]);
}
all.push_back(sm[0]);
}
if (all.size() <= 2) return 0;
for (int j = 1; j < all.size(); j++)
addedge(all[j-1], all[j]);
addedge(all[0], all.back());
}
build(ret);
return 1;
}